/*****************************************************************************
 *  ENTROPY - emerging network to reduce orwellian potency yield
 *
 *  Copyright (C) 2002 Juergen Buchmueller <pullmoll@stop1984.com>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software Foundation,
 *  Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 *
 *	$Id: store.c,v 1.3 2005/11/21 00:36:13 pullmoll Exp $
 *****************************************************************************/
#include "osd.h"
#include "config.h"
#include "store.h"
#include "file.h"
#include "logger.h"

store_t *g_store = NULL;

/* the null key */
sha1_digest_t null = {{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};

#if	STORE_QSORT
/*****************************************************************************
 *	store_sort_drop_time()
 *	Return an index for the comparison of the 'time' fields from two
 *	drop_key_t entries, i.e. let qsort sort the drop[] array by time.
 *****************************************************************************/
static int store_sort_drop_time(const void *p1, const void *p2)
{
	const drop_key_t *d1 = (const drop_key_t *)p1;
	const drop_key_t *d2 = (const drop_key_t *)p2;
	return d1->time - d2->time;
}
#endif

/*
 *	store_info()
 *	Copy a part of the store structure to a caller buffer (used by proxy).
 */
int store_info(store_info_t *info)
{
	int rc = 0;
	FUN("store_info");

	if (NULL == info) {
		errno = EINVAL;
		return -1;
	}

	STORE_LOCK();
	info->storecount = g_store->storecount;
	info->storesize = g_store->storesize;
	info->currsize = g_store->currsize;
	memcpy(info->keycount, g_store->keycount, sizeof(info->keycount));
	memcpy(info->seeks, g_store->seeks, sizeof(info->seeks));
	STORE_UNLOCK();

	return rc;
}

/*
 *	store_upd_fingerprint()
 *	Update the fingerprint for the current distribution of keys in this store.
 */
int store_upd_fingerprint(void)
{
	size_t i, cnt, tot, max, avg;
	FUN("store_upd_fingerprint");

	if (NULL == g_store) {
		errno = EINVAL;
		return -1;
	}

	/* find total and maximum keycount */
	for (i = 0, tot = 0, max = 0; i < NUM_ROUTES; i++) {
		cnt = g_store->keycount[i];
		tot += cnt;
		if (cnt > max)
			max = cnt;
	}
	max += 1;

	/* find average and make normalized fingerprint (0 to 255) */
	for (i = 0, avg = 0; i < NUM_ROUTES; i++) {
		cnt = g_store->keycount[i] * 256 / max;
		cnt = (cnt * 3 + g_store->destination[i]) / 4;
		if (cnt > 255)
			cnt = 255;
		g_store->fingerprint[i] = (uint8_t)cnt;
		avg += cnt;
	}
	g_store->avg = avg / NUM_ROUTES;

	return 0;
}

#define	VER_SIZE	12

/*
 *	store_get_version()
 *	Return 0 if the version file is okay
 *	Return 1 (zap) if it is too old or missing
 */
int store_get_version(void)
{
	char file[MAXPATHLEN];
	struct stat st;
	uint32_t major, minor, build;
	int zap = 1, fd = -1;
	FUN("store_get_version");

	pm_snprintf(file, MAXPATHLEN, "%s/version",
		g_conf->storepath);

	/* assume that we have to zap the store */
	zap = 1;
	for (;;) {
		if (-1 == stat(file, &st)) {
			LOGS(L_STORE,L_ERROR,("stat('%s') failed (%s)\n",
				file, strerror(errno)));
			break;
		}
		fd = open(file, O_RDONLY|O_BINARY);
		if (-1 == fd) {
			LOGS(L_STORE,L_ERROR,("open('%s', O_RDONLY|O_BINARY) failed (%s)\n",
				file, strerror(errno)));
			break;
		}
		if (VER_SIZE != read(fd, g_store->version, VER_SIZE)) {
			LOGS(L_STORE,L_ERROR,("read('%s',0x%x) failed (%s)\n",
				file, VER_SIZE, strerror(errno)));
			break;
		}
		if (NUM_ROUTES != read(fd, g_store->destination, NUM_ROUTES)) {
			LOGS(L_STORE,L_ERROR,("read('%s',0x%x) failed (%s)\n",
				file, NUM_ROUTES, strerror(errno)));
			break;
		}
		major =
			(g_store->version[ 0] <<  0) |
			(g_store->version[ 1] <<  8) |
			(g_store->version[ 2] << 16) |
			(g_store->version[ 3] << 24);
		minor =
			(g_store->version[ 4] <<  0) |
			(g_store->version[ 5] <<  8) |
			(g_store->version[ 6] << 16) |
			(g_store->version[ 7] << 24);
		build =
			(g_store->version[ 8] <<  0) |
			(g_store->version[ 9] <<  8) |
			(g_store->version[10] << 16) |
			(g_store->version[11] << 24);
		if (MKVERSION2(major,minor) < MKVERSION3(0,5,6)) {
			LOGS(L_STORE,L_ERROR,("version < 0.5.6\n"));
			break;
		}
		zap = 0;
		break;
	}

	if (-1 != fd) {
		close(fd);
		fd = -1;
	}

	return zap;
}

static inline uint8_t prng_byte(void)
{
	uint8_t n;
	FUN("prng_byte");

	if (0 != rnd_get(&n, sizeof(n))) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("rnd_get(...,1) failed (%s)\n",
			errmsg));
		die(1,"rnd_get(...,1) failed (%s)\n", errmsg);
	}
	return n;
}

/*
 *	store_put_version()
 *	Write the version info for the store.
 *	If zap is non zero, choose a new destination
 *	fingerprint, too.
 */
int store_put_version(int zap)
{
	char file[MAXPATHLEN];
	uint8_t destination[NUM_ROUTES];
	uint32_t major, minor, build, sum, sumlo, sumhi;
	size_t i, j, max, peak, num_peaks;
	int maxima = 0, scaled;
	uint8_t n;
	int fd = -1;
	FUN("store_put_version");

	snprintf(file, MAXPATHLEN, "%s/version",
		g_conf->storepath);
	fd = open(file, O_RDWR|O_CREAT|O_TRUNC|O_BINARY, 0600);
	if (-1 == fd) {
		LOGS(L_STORE,L_ERROR,("open('%s', O_RDWR|O_CREAT...) call failed (%s)\n",
			file, strerror(errno)));
		info("creating version '%s' (%s) ",
			file, strerror(errno));
		return -1;
	}
	major = strtoul(NODE_VER_MAJ, NULL, 0);
	minor = strtoul(NODE_VER_MIN, NULL, 0) * 65536 +
		strtoul(strchr(NODE_VER_MIN, '.') + 1, NULL, 0);
	build = strtoul(NODE_BUILD, NULL, 0);
	g_store->version[ 0] = (uint8_t)(major >>  0);
	g_store->version[ 1] = (uint8_t)(major >>  8);
	g_store->version[ 2] = (uint8_t)(major >> 16);
	g_store->version[ 3] = (uint8_t)(major >> 24);
	g_store->version[ 4] = (uint8_t)(minor >>  0);
	g_store->version[ 5] = (uint8_t)(minor >>  8);
	g_store->version[ 6] = (uint8_t)(minor >> 16);
	g_store->version[ 7] = (uint8_t)(minor >> 24);
	g_store->version[ 8] = (uint8_t)(build >>  0);
	g_store->version[ 9] = (uint8_t)(build >>  8);
	g_store->version[10] = (uint8_t)(build >> 16);
	g_store->version[11] = (uint8_t)(build >> 24);
	if (VER_SIZE != write(fd, g_store->version, VER_SIZE)) {
		LOGS(L_STORE,L_ERROR,("write('%s', version) call failed (%s)\n",
			file, strerror(errno)));
		info("writing version '%s' (%s) ",
			file, strerror(errno));
	}

	for (i = 0, sum = 0, max = 0; i < NUM_ROUTES; i++) {
		if (g_store->keycount[i] > max)
			max = g_store->keycount[i];
		sum += (destination[i] = g_store->destination[i]);
	}
	sum /= NUM_ROUTES;
	if (0 == max)
		max = 1;

	LOGS(L_STORE,L_NORMAL,("old destination fingerprint: %s [0x%02x]\n",
		hexstr(g_store->destination, 16), sum));

	/*
	 * Convert the store size into a number of possible peaks in
	 * the node's destination fingerprint. The idea is to give
	 * the default node with 512MB no more than one peak, because
	 * it can't keep too much data anyways. Huge stores on the
	 * other hand get up to 9 peaks.
	 */
	if (g_store->storesize < (uint64_t)1024 * 1024 * 1024) {
		num_peaks = 1;
	} else if (g_store->storesize < (uint64_t)2 * 1024 * 1024 * 1024) {
		num_peaks = 2;
	} else if (g_store->storesize < (uint64_t)4 * 1024 * 1024 * 1024) {
		num_peaks = 3;
	} else if (g_store->storesize < (uint64_t)8 * 1024 * 1024 * 1024) {
		num_peaks = 4;
	} else if (g_store->storesize < (uint64_t)12 * 1024 * 1024 * 1024) {
		num_peaks = 5;
	} else if (g_store->storesize < (uint64_t)16 * 1024 * 1024 * 1024) {
		num_peaks = 6;
	} else if (g_store->storesize < (uint64_t)24 * 1024 * 1024 * 1024) {
		num_peaks = 7;
	} else if (g_store->storesize < (uint64_t)32 * 1024 * 1024 * 1024) {
		num_peaks = 8;
	} else {
		num_peaks = 9;
	}
	/* Only if the store was zapped create a new 'fingerprint destination' */
	if (0 != zap) {
		/* choose num_peaks new pseudo random maximum routes */
		for (i = 0; i < num_peaks; i++) {
			do {
				peak = prng_byte() % NUM_ROUTES;
			} while (0 != (maxima & (1 << peak)));
			maxima |= 1 << peak;
		}
	} else {
		/* find num_peaks existing maximum routes */
		for (i = 0; i < num_peaks; i++) {
			peak = (size_t)-1;
			for (j = 0; j < NUM_ROUTES; j++) {
				/* skip existing maxima */
				if (0 != (maxima & (1 << j)))
					continue;
				if ((size_t)-1 == peak ||
					g_store->keycount[j] > g_store->keycount[peak])
					peak = j;
			}
			/* found one */
			maxima |= 1 << peak;
		}
	}

	LOGS(L_STORE,L_NORMAL,("maxima %u %#04x\n",
		bitsum(maxima), maxima));

	/* now choose a pseudo random fingerprint with these 6 maxima */
	for (i = 0; i < NUM_ROUTES; i++) {
		n = prng_byte();
		if (0 == (maxima & (1 << i))) {
			/* keycount scaled to range 0x00 to 0xef */
			scaled = (int)(g_store->keycount[i] * 0xf0 / max);
			/* choose a value around scaled +/- 0x10 */
			scaled = scaled + (n & 0x1f) - 0x10;
			if (scaled < 0x00)
				scaled = 0x00;
			else if (scaled > 0xef)
				scaled = 0xef;
			n = (uint8_t)scaled;
		} else {
			/* between 0xf0 and 0xff */
			n = (n & 0x0f) | 0xf0;
		}
		destination[i] = n;
	}

	/* adjust destination[] until the average is +/- 0x10 around expected */
	sumlo = (num_peaks + 1) * 0x10 - 0x10;
	sumhi = (num_peaks + 1) * 0x10 + 0x10;
	do {
		for (i = 0, sum = 0; i < NUM_ROUTES; i++)
			sum += destination[i];
		sum /= NUM_ROUTES;
		/* overall routes too low: increment routes below 0xf0 */
		if (sum <= sumlo) {
			LOGS(L_STORE,L_DEBUG,("fingerprint too low: %s [0x%02x]\n",
				hexstr(destination, 16), sum));
			for (i = 0; i < NUM_ROUTES; i++)
				if (destination[i] < 0xf0)
					destination[i] += 1;
		}
		/* overall routes too high: decrement routes between 0x01 and 0xef */
		if (sum >= sumhi) {
			LOGS(L_STORE,L_DEBUG,("fingerprint too high: %s [0x%02x]\n",
				hexstr(destination, 16), sum));
			for (i = 0; i < NUM_ROUTES; i++)
				if (destination[i] > 0x00 && destination[i] < 0xf0)
					destination[i] -= 1;
		}
	} while (sum <= sumlo || sum >= sumhi);

	for (i = 0; i < NUM_ROUTES; i++)
		g_store->destination[i] = destination[i];

	LOGS(L_STORE,L_NORMAL,("new destination fingerprint: %s [0x%02x]\n",
		hexstr(g_store->destination, 16), sum));

	if (NUM_ROUTES != write(fd, g_store->destination, NUM_ROUTES)) {
		LOGS(L_STORE,L_ERROR,("write('%s') destination call failed (%s)\n",
			file, strerror(errno)));
		info("writing destination '%s' (%s) ",
			file, strerror(errno));
		return -1;
	}

	close(fd);
	fd = -1;

	return 0;
}

/* add a key 'sha1' of size 'size' to the statistics */
int store_add_key(const sha1_digest_t *sha1, size_t size)
{
	uint8_t fpr;
	uint32_t idx;

	idx = sha1->digest[0] | ((uint32_t)sha1->digest[1] << 8);
	fpr = keyroute(sha1);
	g_store->storecount += 1;
	g_store->currsize += size;
	g_store->keycount[fpr] += 1;
	/* clear a missing[] entry for this index */
	g_store->missing[idx] = null;
	/* set an available[] entry for this index */
	g_store->available[idx] = *sha1;

	/* update fingerprint */
	store_upd_fingerprint();

	return 0;
}

/* subtract a key 'sha1' of size 'size' from the statistics */
int store_sub_key(const sha1_digest_t *sha1, size_t size)
{
	uint8_t fpr;
	uint32_t idx;

	idx = sha1->digest[0] | ((uint32_t)sha1->digest[1] << 8);
	fpr = keyroute(sha1);
	if (g_store->storecount > 0)
		g_store->storecount -= 1;
	if (g_store->currsize > size)
		g_store->currsize -= size;
	else
		g_store->currsize = 0;
	if (g_store->keycount[fpr] > 0)
		g_store->keycount[fpr] -= 1;
	/* set a missing[] entry for this index */
	g_store->missing[idx] = *sha1;
	/* clear an available[] entry for this index */
	g_store->available[idx] = null;

	/* update fingerprint */
	store_upd_fingerprint();

	return 0;
}
